/**
 * 单向链表
 */

/**
 * 节点类,链表中的节点
 */
class ListNode {
  val = null;
  next = null;
  /**
   *
   * @param {string | number | null} val 链表节点的值
   * @param {ListNode | null} next 链表节点的下一个节点
   */
  constructor(val, next) {
    this.val = val;
    this.next = next;
  }
}

/* 初始化链表 1 -> 3 -> 2 -> 5 -> 4 */
const n0 = new ListNode(1);
const n1 = new ListNode(3);
const n2 = new ListNode(2);
const n3 = new ListNode(5);
const n4 = new ListNode(4);

n0.next = n1;
n1.next = n2;
n2.next = n3;
n3.next = n4;

/**
 * 插入节点
 * @param {ListNode} n 插入的节点前一个节点
 * @param {ListNode} p 要插入的节点
 */
function insert(n, p) {
  p.next = n.next;
  n.next = p;
}

const n5 = new ListNode(6);
insert(n1, n5);

/**
 * 删除节点
 * @param {ListNode} n 要删除的节点之前的节点
 */
function remove(n) {
  try {
    const p = n.next;
    n.next = p.next;
  } catch (error) {
    console.error(error);
  }
}
remove(n1);

/**
 * 访问节点
 * @param {number} index 要访问的节点的索引
 */
function access(index) {
  let temp = n0;
  for (let i = 0; i < index; i++) {
    if (!temp) return null;
    temp = temp.next;
  }
  return temp;
}

/**
 * 查找节点值
 * @param {string | number | null} target 要查找的节点的值
 */
function find(target) {
  let temp = n0;
  let index = -1;
  while (temp) {
    index++;
    if (temp.val === target) {
      return index;
    }
    temp = temp.next;
  }
  return -1;
}

/**
 * 将链表转换为数组
 */
function toArray() {
  const arr = [];
  let temp = n0;
  while (temp) {
    arr.push(temp.val);
    temp = temp.next;
  }
  console.log(arr);
}

toArray();

const index_3 = access(3);
console.log('索引3的节点', index_3.val);

const find_5 = find(5);
console.log('查找内容为5的索引', find_5);

class LinkedList {
  constructor() {
    this.head = null; // 头节点
    this.end = null; // 尾节点
    this.size = 0; // 链表长度
  }

  /**
   *  插入节点,尾结点
   */
  push(target) {
    const node = new ListNode(target, null);
    if (!this.head && !this.end) {
      this.head = this.end = node;
    } else {
      this.end.next = node;
      this.end = node;
    }
    this.size++;
  }

  /**
   * 插入节点,头节点
   */
  unshift(target) {
    const node = new ListNode(target, null);
    if (!this.head && !this.end) {
      this.head = this.end = node;
    } else {
      node.next = this.head;
      this.head = node;
    }
    this.size++;
  }
  /**
   * 删除节点
   */
  remove(n) {
    try {
      n.next = n.next.next;
      this.size--;
    } catch (error) {
      console.error(
        error,
        '因为是单向链表,只能是获取要删除的节点的前一个节点,需要双向链表实现,暂时先这样吧,单向链表倒是也能实现,就是太麻烦,还不如用双向链表'
      );
    }
  }

  /**
   * 是否为空链表
   */
  isEmpty() {
    return this.size === 0;
  }

  /**
   * 查找节点值
   */
  find(target) {
    if (this.isEmpty()) throw new Error('该链表是空链表');
    let temp = this.head;
    while (temp) {
      if (temp.val === target) return temp;
      temp = temp.next;
    }
  }

  /**
   * 根据索引访问节点
   */
  access(index) {
    let temp = this.head;
    for (let i = 0; i < index; i++) {
      if (!temp) throw new Error('索引越界');
      temp = temp.next;
    }
    return temp;
  }

  /**
   * 转为数组输出
   */
  toArray() {
    const arr = [];
    let temp = this.head;
    for (let i = 0; i < this.size; i++) {
      arr.push(temp.val);
      temp = temp.next;
    }
    return arr;
  }
}

const linkedList = new LinkedList();
linkedList.push(1);
linkedList.push(3);

linkedList.unshift(9);

console.log('查找值为3的数据', linkedList.find(3));
console.log('查找索引为1的数据节点', linkedList.access(1));
console.log('删除值为1后面的一个节点', linkedList.remove(linkedList.find(1)));

console.log('转为数组', linkedList.toArray());
